{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Closest Room"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: closestRoom"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最近的房间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>一个酒店里有 <code>n</code> 个房间，这些房间用二维整数数组 <code>rooms</code> 表示，其中 <code>rooms[i] = [roomId<sub>i</sub>, size<sub>i</sub>]</code> 表示有一个房间号为 <code>roomId<sub>i</sub></code> 的房间且它的面积为 <code>size<sub>i</sub></code> 。每一个房间号 <code>roomId<sub>i</sub></code> 保证是 <strong>独一无二</strong> 的。</p>\n",
    "\n",
    "<p>同时给你 <code>k</code> 个查询，用二维数组 <code>queries</code> 表示，其中 <code>queries[j] = [preferred<sub>j</sub>, minSize<sub>j</sub>]</code> 。第 <code>j</code> 个查询的答案是满足如下条件的房间 <code>id</code> ：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>房间的面积 <b>至少</b> 为 <code>minSize<sub>j</sub></code> ，且</li>\n",
    "\t<li><code>abs(id - preferred<sub>j</sub>)</code> 的值 <strong>最小</strong> ，其中 <code>abs(x)</code> 是 <code>x</code> 的绝对值。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果差的绝对值有 <strong>相等</strong> 的，选择 <strong>最小</strong> 的 <code>id</code> 。如果 <strong>没有满足条件的房间</strong> ，答案为 <code>-1</code> 。</p>\n",
    "\n",
    "<p>请你返回长度为 <code>k</code> 的数组 <code>answer</code> ，其中<em> </em><code>answer[j]</code> 为第 <code>j</code> 个查询的结果。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>rooms = [[2,2],[1,2],[3,2]], queries = [[3,1],[3,3],[5,2]]\n",
    "<b>输出：</b>[3,-1,3]\n",
    "<strong>解释：</strong>查询的答案如下：\n",
    "查询 [3,1] ：房间 3 的面积为 2 ，大于等于 1 ，且号码是最接近 3 的，为 abs(3 - 3) = 0 ，所以答案为 3 。\n",
    "查询 [3,3] ：没有房间的面积至少为 3 ，所以答案为 -1 。\n",
    "查询 [5,2] ：房间 3 的面积为 2 ，大于等于 2 ，且号码是最接近 5 的，为 abs(3 - 5) = 2 ，所以答案为 3 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<b>输入：</b>rooms = [[1,4],[2,3],[3,5],[4,1],[5,2]], queries = [[2,3],[2,4],[2,5]]\n",
    "<b>输出：</b>[2,1,3]\n",
    "<strong>解释：</strong>查询的答案如下：\n",
    "查询 [2,3] ：房间 2 的面积为 3 ，大于等于 3 ，且号码是最接近的，为 abs(2 - 2) = 0 ，所以答案为 2 。\n",
    "查询 [2,4] ：房间 1 和 3 的面积都至少为 4 ，答案为 1 因为它房间编号更小。\n",
    "查询 [2,5] ：房间 3 是唯一面积大于等于 5 的，所以答案为 3 。</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == rooms.length</code></li>\n",
    "\t<li><code>1 <= n <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>k == queries.length</code></li>\n",
    "\t<li><code>1 <= k <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 <= roomId<sub>i</sub>, preferred<sub>j</sub> <= 10<sup>7</sup></code></li>\n",
    "\t<li><code>1 <= size<sub>i</sub>, minSize<sub>j</sub> <= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [closest-room](https://leetcode.cn/problems/closest-room/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [closest-room](https://leetcode.cn/problems/closest-room/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[2,2],[1,2],[3,2]]\\n[[3,1],[3,3],[5,2]]', '[[1,4],[2,3],[3,5],[4,1],[5,2]]\\n[[2,3],[2,4],[2,5]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        queries = list(enumerate(queries))\n",
    "        roomids = SortedList()\n",
    "        answer = [-1] * len(queries)\n",
    "\n",
    "        rooms.sort(key=lambda x: x[1])\n",
    "        queries.sort(key=lambda x: x[1][1], reverse=True)\n",
    "\n",
    "        for (j, [prefered, minsize]) in queries:\n",
    "            while len(rooms) > 0 and rooms[-1][1] >= minsize:\n",
    "                roomids.add(rooms.pop()[0])\n",
    "            if len(roomids) == 0:\n",
    "                continue\n",
    "\n",
    "            i = roomids.bisect_left(prefered)\n",
    "            if i == 0:\n",
    "                answer[j] = roomids[0]\n",
    "            elif i == len(roomids):\n",
    "                answer[j] = roomids[-1]\n",
    "            elif abs(roomids[i] - prefered) < abs(roomids[i - 1] - prefered):\n",
    "                answer[j] = roomids[i]\n",
    "            else:\n",
    "                answer[j] = roomids[i - 1]\n",
    "\n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rooms.sort(key=lambda x: x[1])\n",
    "        k = len(queries)\n",
    "        idx = sorted(range(k), key=lambda i: queries[i][1])\n",
    "        ans = [-1] * k\n",
    "        i, n = 0, len(rooms)\n",
    "        sl = SortedList(x[0] for x in rooms)\n",
    "        for j in idx:\n",
    "            prefer, minSize = queries[j]\n",
    "            while i < n and rooms[i][1] < minSize:\n",
    "                sl.remove(rooms[i][0])\n",
    "                i += 1\n",
    "            if i == n:\n",
    "                break\n",
    "            p = sl.bisect_left(prefer)\n",
    "            if p < len(sl):\n",
    "                ans[j] = sl[p]\n",
    "            if p > 0:\n",
    "                if ans[j] == -1 or ans[j] - prefer >= prefer - sl[p - 1]:\n",
    "                    ans[j] = sl[p - 1]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rooms.sort(key = lambda x: x[1], reverse = True)\n",
    "        queries = [(i, q) for i, q in enumerate(queries)]\n",
    "        queries.sort(key = lambda x: x[1][1], reverse = True)\n",
    "        print(rooms, queries)\n",
    "        j = 0\n",
    "        n = len(rooms)\n",
    "        sl = SortedList()\n",
    "        ans = [-1] * len(queries)\n",
    "        for i, (prefer, size) in queries:\n",
    "            while j < n and rooms[j][1] >= size:\n",
    "                sl.add(rooms[j][0])\n",
    "                j += 1\n",
    "            if len(sl) == 0: continue\n",
    "            \n",
    "            left = bisect_left(sl, prefer, hi = len(sl) - 1)\n",
    "            #print(sl, prefer, left)\n",
    "            ans[i] = sl[left]\n",
    "            if left > 0 and abs(prefer - sl[left - 1]) <= abs(prefer - sl[left]):\n",
    "                ans[i] = sl[left - 1]\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(\n",
    "        self, rooms: List[List[int]], queries: List[List[int]]\n",
    "    ) -> List[int]:\n",
    "        rooms.sort(key=lambda x: x[1])\n",
    "        k = len(queries)\n",
    "        idx = sorted(range(k), key=lambda i: queries[i][1])\n",
    "        ans = [-1] * k\n",
    "        i, n = 0, len(rooms)\n",
    "        sl = SortedList(x[0] for x in rooms)\n",
    "        for j in idx:\n",
    "            prefer, minSize = queries[j]\n",
    "            while i < n and rooms[i][1] < minSize:\n",
    "                sl.remove(rooms[i][0])\n",
    "                i += 1\n",
    "            if i == n:\n",
    "                break\n",
    "            p = sl.bisect_left(prefer)\n",
    "            if p < len(sl):\n",
    "                ans[j] = sl[p]\n",
    "            if p and (ans[j] == -1 or ans[j] - prefer >= prefer - sl[p - 1]):\n",
    "                ans[j] = sl[p - 1]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        lr, lq = len(rooms), len(queries)\n",
    "        rooms.sort(key=lambda x: (-x[1], x[0]))\n",
    "        queries = sorted([(i, q[0], q[1]) for i, q in enumerate(queries)], key=lambda x: -x[2])\n",
    "        answer = [-1]*lq\n",
    "        now = 0\n",
    "        sorted_arr = []\n",
    "        for idx, preferred, minSize in queries:\n",
    "            while now < lr and rooms[now][1] >= minSize:\n",
    "                insort(sorted_arr, rooms[now][0])\n",
    "                now += 1\n",
    "            if sorted_arr:\n",
    "                where = bisect_left(sorted_arr, preferred)\n",
    "                answer[idx] = sorted_arr[max(where-1, 0)]\n",
    "                if where < len(sorted_arr) and abs(sorted_arr[max(0, where-1)] - preferred) > abs(sorted_arr[where] - preferred):\n",
    "                    answer[idx] = sorted_arr[where]\n",
    "            \n",
    "        return answer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedDict, SortedList, SortedSet\n",
    "\n",
    "\"\"\"\n",
    "stuff you should look for\n",
    "int overflow, array bounds\n",
    "special cases (n=1?)\n",
    "do smth instead of nothing and stay organized\n",
    "WRITE STUFF DOWN\n",
    "DON'T GET STUCK ON ONE APPROACH\n",
    "\"\"\"\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(rooms)\n",
    "        k = len(queries)\n",
    "        rooms.sort(key=lambda x: -x[1])\n",
    "        idx = range(n)\n",
    "        ans = [-1] * k\n",
    "        s = SortedList()\n",
    "        s.add(10**9)\n",
    "        s.add(-10**9)\n",
    "        room_idx = 0\n",
    "        for i, (prefer, minsize) in sorted(zip(idx, queries), key=lambda x: -x[1][1]):\n",
    "            while room_idx < n and rooms[room_idx][1] >= minsize:\n",
    "                s.add(rooms[room_idx][0])\n",
    "                room_idx += 1\n",
    "            up = bisect_left(s, prefer)\n",
    "            down = up - 1\n",
    "            id = s[down] if abs(s[up] - prefer) >= abs(s[down] - prefer) else s[up]\n",
    "            if abs(id) != 10**9:\n",
    "                ans[i] = id\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rooms.sort(key=lambda x: (x[1], x[0]), reverse=True)\n",
    "        queries = [[id, size, i] for i, (id, size) in enumerate(queries)]\n",
    "        queries.sort(key=lambda x: (x[1], x[0]), reverse=True)\n",
    "        m = collections.deque(rooms)\n",
    "\n",
    "        arr = []\n",
    "        ans = [0] * len(queries)\n",
    "        for id, size, i in queries:\n",
    "            while m and m[0][1] >= size:\n",
    "                bisect.insort_left(arr, m.popleft())\n",
    "            if not arr:\n",
    "                ans[i] = -1\n",
    "                continue\n",
    "            l = bisect.bisect_left(arr, [id, size])\n",
    "            if l == 0:\n",
    "                ans[i] = arr[0][0]\n",
    "            elif l == len(arr):\n",
    "                ans[i] = arr[-1][0]\n",
    "            else:\n",
    "                a = arr[l - 1][0]\n",
    "                b = arr[l][0]\n",
    "                if abs(a - id) <= abs(b - id):\n",
    "                    ans[i] = a\n",
    "                else:\n",
    "                    ans[i] = b\n",
    "        return ans\n",
    "\n",
    "# 作者：两颗赛艇\n",
    "# 链接：https://leetcode.cn/problems/closest-room/solutions/754743/li-yong-dui-lie-chu-li-by-tooooo_the_moo-9f1h/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。\n",
    "# 1.根据size逆序排列两个数组 \n",
    "# 2.遍历quieries时，逐个弹出size大于等于目标size的room，根据id二分插入一个新的arr，再二分查找目标id在新arr的位置\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rooms.sort(key=lambda a: a[1], reverse=True)\n",
    "        idx = [i for i in range(len(queries))]\n",
    "        idx.sort(key=lambda a: queries[a][1], reverse=True)\n",
    "        ans = [-1] * len(queries)\n",
    "        sl = SortedList()\n",
    "        j = 0\n",
    "        for i in range(len(queries)):\n",
    "            preferredj, minSizej = queries[idx[i]]\n",
    "            while j < len(rooms) and rooms[j][1] >= minSizej:\n",
    "                sl.add(rooms[j][0])\n",
    "                j += 1\n",
    "            if len(sl) == 0:\n",
    "                continue\n",
    "            b = bisect_left(sl, preferredj,hi=len(sl) - 1)\n",
    "            ans[idx[i]] = sl[b] \n",
    "            if b > 0 and abs(sl[b-1] - preferredj) <= abs(sl[b] - preferredj):\n",
    "                ans[idx[i]] = sl[b-1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        #1.暴力双重遍历(超时)\n",
    "        #ans=[]\n",
    "        #for i in queries:\n",
    "        #    k=-1\n",
    "        #    for j in rooms:\n",
    "        #        if j[1]>=i[1]:\n",
    "        #            if k==-1:\n",
    "        #                k=j[0]\n",
    "        #            if abs(j[0]-i[0])<abs(k-i[0]):\n",
    "        #                k=j[0]\n",
    "        #            if abs(j[0]-i[0])==abs(k-i[0]):\n",
    "        #                k=min(j[0],k)\n",
    "        #    ans.append(k)\n",
    "        #return ans\n",
    "        #2.有序集合+二分+离线\n",
    "        rooms.sort(key=lambda a: a[1], reverse=True)\n",
    "        idx = [i for i in range(len(queries))]\n",
    "        idx.sort(key=lambda a: queries[a][1], reverse=True)\n",
    "        ans = [-1] * len(queries)\n",
    "        sl = SortedList()\n",
    "        j = 0\n",
    "        for i in range(len(queries)):\n",
    "            preferredj, minSizej = queries[idx[i]]\n",
    "            while j < len(rooms) and rooms[j][1] >= minSizej:\n",
    "                sl.add(rooms[j][0])\n",
    "                j += 1\n",
    "            if len(sl) == 0:\n",
    "                continue\n",
    "            b = bisect_left(sl, preferredj,hi=len(sl) - 1) \n",
    "              #只查询离preferredj最近的一大一小值\n",
    "            ans[idx[i]] = sl[b] \n",
    "            if b > 0 and abs(sl[b-1] - preferredj) <= abs(sl[b] - preferredj):\n",
    "                ans[idx[i]] = sl[b-1]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        qn = len(queries)\n",
    "        idx = list(range(qn))\n",
    "        idx.sort(key=lambda i: -queries[i][1])\n",
    "        rooms.sort(key=lambda x:-x[1])\n",
    "        left = 0\n",
    "        rn = len(rooms)\n",
    "        from sortedcontainers import SortedList\n",
    "        sl = SortedList()\n",
    "        ret = [-1] * qn\n",
    "        for i in idx:\n",
    "            id, size = queries[i]\n",
    "            while left < rn and rooms[left][1] >= size:\n",
    "                sl.add(rooms[left][0])\n",
    "                left += 1\n",
    "            if sl:\n",
    "                p = sl.bisect_left(id)\n",
    "                if p == len(sl):\n",
    "                    ret[i] = sl[-1]\n",
    "                elif p == 0:\n",
    "                    ret[i] = sl[0]\n",
    "                else:\n",
    "                    id1, id2 = sl[p - 1], sl[p]\n",
    "                    if id - id1 <= id2 - id:\n",
    "                        ret[i] = id1\n",
    "                    else:\n",
    "                        ret[i] = id2\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rooms.sort(key=lambda a: a[1], reverse=True)\n",
    "        idx = [i for i in range(len(queries))]\n",
    "        idx.sort(key=lambda a: queries[a][1], reverse=True)\n",
    "        ans = [-1] * len(queries)\n",
    "        sl = SortedList()\n",
    "        j = 0\n",
    "        for i in range(len(queries)):\n",
    "            preferredj, minSizej = queries[idx[i]]\n",
    "            while j < len(rooms) and rooms[j][1] >= minSizej:\n",
    "                sl.add(rooms[j][0])\n",
    "                j += 1\n",
    "            if len(sl) == 0:\n",
    "                continue\n",
    "            b = bisect_left(sl, preferredj,hi=len(sl) - 1)\n",
    "            ans[idx[i]] = sl[b] \n",
    "            if b > 0 and abs(sl[b-1] - preferredj) <= abs(sl[b] - preferredj):\n",
    "                ans[idx[i]] = sl[b-1]\n",
    "        return ans\n",
    "\n",
    "# 作者：瓦片\n",
    "# 链接：https://leetcode.cn/problems/closest-room/solutions/2264297/python-1847-zui-jin-de-fang-jian-by-wa-p-c43d/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Block:\n",
    "    def __init__(self):\n",
    "        # block 中最小的房间 size\n",
    "        self.min_size = float(\"inf\")\n",
    "        # block 中的房间 id\n",
    "        self.ids = list()\n",
    "        # 原始数据\n",
    "        self.origin = list()\n",
    "\n",
    "    # 加入一个房间\n",
    "    def insert(self, idx: int, size: int):\n",
    "        self.origin.append((idx, size))\n",
    "        self.ids.append(idx)\n",
    "        self.min_size = min(self.min_size, size)\n",
    "\n",
    "    # 添加完所有房间后，将房间 id 排序，便于后续二分\n",
    "    def sort(self):\n",
    "        self.ids.sort()\n",
    "\n",
    "    # 封装一下二分函数，找最小的大于等于它的\n",
    "    def geq(self, preferred: int) -> int:\n",
    "        _ids = self.ids\n",
    "\n",
    "        it = bisect_left(_ids, preferred);\n",
    "        return -1 if it == len(_ids) else _ids[it]\n",
    "\n",
    "    # 封装一下二分函数，找最大的严格小于它的\n",
    "    def lt(self, preferred: int) -> int:\n",
    "        _ids = self.ids\n",
    "\n",
    "        it = bisect_right(_ids, preferred)\n",
    "        return -1 if it == 0 else _ids[it - 1]\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        BLOCK_SIZE = 300\n",
    "        \n",
    "        # 按照 size 升序排序\n",
    "        rooms.sort(key=lambda room: room[1])\n",
    "\n",
    "        # 每 BLOCK_SIZE 个房间放进一个 block\n",
    "        blocks = list()\n",
    "        for i, (roomid, size) in enumerate(rooms):\n",
    "            if i % BLOCK_SIZE == 0:\n",
    "                blocks.append(Block())\n",
    "            blocks[-1].insert(roomid, size)\n",
    "        \n",
    "        for block in blocks:\n",
    "            block.sort()\n",
    "\n",
    "        ans = [-1] * len(queries)\n",
    "        for i, (preferred, minsize) in enumerate(queries):\n",
    "            mindiff = float(\"inf\")\n",
    "\n",
    "            for block in blocks[::-1]:\n",
    "                rooms = block.origin\n",
    "                # block 中最小 size 的房间大于等于 minsize，整个 block 都可以选择\n",
    "                if rooms[0][1] >= minsize:\n",
    "                    c1 = block.geq(preferred)\n",
    "                    if c1 != -1 and c1 - preferred < mindiff:\n",
    "                        mindiff = c1 - preferred\n",
    "                        ans[i] = c1\n",
    "                    \n",
    "                    c2 = block.lt(preferred)\n",
    "                    if c2 != -1 and preferred - c2 <= mindiff:\n",
    "                        mindiff = preferred - c2\n",
    "                        ans[i] = c2\n",
    "                else:\n",
    "                    # 只有部分都可以选择，遍历一下所有的房间\n",
    "                    for room in rooms[::-1]:\n",
    "                        if room[1] >= minsize:\n",
    "                            diff = abs(room[0] - preferred)\n",
    "                            if diff < mindiff or (diff == mindiff and room[0] < ans[i]):\n",
    "                                mindiff = diff\n",
    "                                ans[i] = room[0]\n",
    "                        else:\n",
    "                            break\n",
    "                    # 再之前的 block 一定都严格小于 minsize，可以直接退出\n",
    "                    break\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rooms.sort(key = lambda x: x[1], reverse = True)\n",
    "        queries = [(i, q) for i, q in enumerate(queries)]\n",
    "        queries.sort(key = lambda x: x[1][1], reverse = True)\n",
    "        j = 0\n",
    "        n = len(rooms)\n",
    "        sl = SortedList()\n",
    "        ans = [-1] * len(queries)\n",
    "        for i, (prefer, size) in queries:\n",
    "            while j < n and rooms[j][1] >= size:\n",
    "                sl.add(rooms[j][0])\n",
    "                j += 1\n",
    "            if len(sl) == 0: continue\n",
    "            \n",
    "            left = bisect_left(sl, prefer, hi = len(sl) - 1)\n",
    "\n",
    "            ans[i] = sl[left]\n",
    "            if left > 0 and abs(prefer - sl[left - 1]) <= abs(prefer - sl[left]):\n",
    "                ans[i] = sl[left - 1]\n",
    "            \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "# sys.set_int_max_str_digits(0)  # 大数的范围坑\n",
    "\n",
    "\n",
    "def ac_max(a, b):\n",
    "    return a if a > b else b\n",
    "\n",
    "\n",
    "def ac_min(a, b):\n",
    "    return a if a < b else b\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rooms.sort(key=lambda it: -it[1])\n",
    "        m = len(rooms)\n",
    "        i = 0\n",
    "        n = len(queries)\n",
    "        ans = [-1]*n\n",
    "        ind = list(range(n))\n",
    "        ind.sort(key=lambda it: -queries[it][1])\n",
    "        lst = SortedList()\n",
    "        for x in ind:\n",
    "            j, size = queries[x]\n",
    "            while i < m and rooms[i][1] >= size:\n",
    "                lst.add(rooms[i][0])\n",
    "                i += 1\n",
    "            cur = inf\n",
    "            res = -1\n",
    "            y = lst.bisect_left(j)\n",
    "            for w in [y-1, y, y+1]:\n",
    "                if 0<=w<len(lst):\n",
    "                    cur_dis = abs(lst[w]-j)\n",
    "                    if cur_dis < cur or (cur_dis==cur and lst[w]<res):\n",
    "                        cur = cur_dis\n",
    "                        res = lst[w]\n",
    "            ans[x] = res\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rooms.sort(key=lambda x:x[1], reverse=True)\n",
    "        n = len(queries)\n",
    "        m = len(rooms)\n",
    "        ans = [0] * n\n",
    "        rid = 0\n",
    "        cand = SortedList()  # 候选的 roomid\n",
    "        for i, (prefer, mn_size) in sorted(enumerate(queries), key=lambda x:x[1][1], reverse=True):\n",
    "            while rid < m and rooms[rid][1] >= mn_size:\n",
    "                roomid = rooms[rid][0]\n",
    "                cand.add(roomid)\n",
    "                rid += 1\n",
    "            if len(cand) == 0:\n",
    "                ans[i] = -1\n",
    "                continue\n",
    "            p = cand.bisect_left(prefer)\n",
    "            if p == len(cand):\n",
    "                ans[i] = cand[p - 1]\n",
    "            elif p > 0:\n",
    "                if abs(cand[p] - prefer) < abs(cand[p - 1] - prefer):\n",
    "                    ans[i] = cand[p]\n",
    "                else:\n",
    "                    ans[i] = cand[p - 1]\n",
    "            else:\n",
    "                ans[i] = cand[p]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param rooms:\n",
    "        :param queries:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        q1 = []\n",
    "        for k,v in enumerate(queries):\n",
    "            q1.append((v[1], v[0],k))\n",
    "        q1.sort(key=lambda x: -x[0])\n",
    "        rooms.sort(key=lambda x: -x[1])\n",
    "        sd1 = SortedList()\n",
    "        ret = []\n",
    "        for i in q1:\n",
    "            while rooms and rooms[0][1] >= i[0]:\n",
    "                res = rooms.pop(0)\n",
    "                sd1.add(res[0])\n",
    "            if len(sd1) == 0:\n",
    "                ret.append((-1, i[2]))\n",
    "            else:\n",
    "                idx1 = sd1.bisect_left(i[1])\n",
    "                val1 = sd1[max(0, idx1-1)]\n",
    "                val2 = sd1[min(len(sd1)-1, idx1)]\n",
    "                val = val1 if abs(val1-i[1]) <= abs(val2-i[1]) else val2\n",
    "                ret.append((val, i[2]))\n",
    "        ret.sort(key=lambda x: x[1])\n",
    "        return [i[0] for i in ret]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def closestRoom(self, r: List[List[int]], q: List[List[int]]) -> List[int]:\n",
    "        q = [(q[j][1], q[j][0], j) for j in range(len(q))]\n",
    "        n = len(q)\n",
    "        q.sort(reverse=True)\n",
    "        r = [(y, x) for x, y in r]\n",
    "        r.sort()\n",
    "        # r = deque(r[::-1])\n",
    "        # print(p)\n",
    "        ans = {}\n",
    "        t = SortedList([])\n",
    "        for s, p, j in q:\n",
    "            while r and (r[-1][0]>=s):\n",
    "                i, idd = r.pop()\n",
    "                t.add(idd) \n",
    "            if not t:\n",
    "                ans[j] = -1 \n",
    "            else:\n",
    "                ix = t.bisect_left(p) \n",
    "                if ix==len(t):\n",
    "                    ans[j] = t[-1] \n",
    "                elif ix==0:\n",
    "                    ans[j] = t[0] \n",
    "                else:\n",
    "                    if (p-t[ix-1])<=(t[ix]-p):\n",
    "                        ans[j] = t[ix-1]\n",
    "                    else:\n",
    "                        ans[j] = t[ix] \n",
    "        return [ans[j] for j in range(n)]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        n = len(rooms)\n",
    "        ans = [-1] * len(queries)\n",
    "        newq = sorted(enumerate(queries), key = lambda x: x[1][1], reverse = True)\n",
    "        l = SortedList()\n",
    "        rooms.sort(key = lambda x: x[1], reverse = True)\n",
    "        # print(rooms)\n",
    "        i = 0\n",
    "        for id, (x, y) in newq:\n",
    "            while i < n and rooms[i][1] >= y:\n",
    "                l.add(rooms[i][0])\n",
    "                i += 1\n",
    "            if l:\n",
    "                idx1 = l.bisect_right(x)\n",
    "                # print(id, idx1, l)\n",
    "                if idx1 == len(l):\n",
    "                    ans[id] = l[idx1 - 1]\n",
    "                elif idx1 - 1 >= 0:\n",
    "                    if x - l[idx1 - 1] <= l[idx1] - x:\n",
    "                        ans[id] = l[idx1 - 1]\n",
    "                    else:\n",
    "                        ans[id] = l[idx1]\n",
    "                else:\n",
    "                    ans[id] = l[idx1]\n",
    "\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        n=len(rooms)\n",
    "        rooms.sort(key=lambda x:-x[1])\n",
    "\n",
    "        a=[(i,rid,p) for i,(rid,p) in enumerate(queries)]\n",
    "        a.sort(key=lambda x:-x[2])\n",
    "        print(a)\n",
    "        from sortedcontainers import SortedList\n",
    "        sd=SortedList()\n",
    "        res=[-1]*len(queries)\n",
    "        j=0\n",
    "        for i,rid,p in a:\n",
    "            while j<n and rooms[j][1]>=p:\n",
    "                sd.add(rooms[j][0])\n",
    "                j+=1\n",
    "            \n",
    "            if sd:\n",
    "                idx=sd.bisect_left(rid)\n",
    "                if idx==len(sd):\n",
    "                    res[i]=sd[idx-1]\n",
    "                elif idx==0:\n",
    "                    res[i]=sd[0]               \n",
    "                elif idx>0:\n",
    "                    u,v=sd[idx-1],sd[idx]\n",
    "                    if abs(u-rid)>abs(v-rid):\n",
    "                        res[i]=v\n",
    "                    else:\n",
    "                        res[i]=u\n",
    "                \n",
    "        return res\n",
    "\n",
    "\n",
    "                    \n",
    "\n",
    "            \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param rooms:\n",
    "        :param queries:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        q1 = []\n",
    "        for k,v in enumerate(queries):\n",
    "            q1.append((v[1], v[0],k))\n",
    "        q1.sort(key=lambda x: -x[0])\n",
    "        rooms.sort(key=lambda x: -x[1])\n",
    "        sd1 = SortedList()\n",
    "        ret = []\n",
    "        for i in q1:\n",
    "            while rooms and rooms[0][1] >= i[0]:\n",
    "                res = rooms.pop(0)\n",
    "                sd1.add(res[0])\n",
    "            if len(sd1) == 0:\n",
    "                ret.append((-1, i[2]))\n",
    "            else:\n",
    "                idx1 = sd1.bisect_left(i[1])\n",
    "                idx2 = sd1.bisect_right(i[1])\n",
    "                val1 = sd1[max(0, idx1-1)]\n",
    "                val2 = sd1[min(len(sd1)-1, idx1)]\n",
    "                val = val1 if abs(val1-i[1]) <= abs(val2-i[1]) else val2\n",
    "                ret.append((val, i[2]))\n",
    "        ret.sort(key=lambda x: x[1])\n",
    "        return [i[0] for i in ret]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param rooms:\n",
    "        :param queries:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        q1 = []\n",
    "        for k,v in enumerate(queries):\n",
    "            q1.append((v[1], v[0],k))\n",
    "        q1.sort(key=lambda x: -x[0])\n",
    "        rooms.sort(key=lambda x: -x[1])\n",
    "        rooms = deque(rooms)\n",
    "        sd1 = SortedList()\n",
    "        ret = []\n",
    "        for i in q1:\n",
    "            while rooms and rooms[0][1] >= i[0]:\n",
    "                res = rooms.popleft()\n",
    "                sd1.add(res[0])\n",
    "            if len(sd1) == 0:\n",
    "                ret.append((-1, i[2]))\n",
    "            else:\n",
    "                idx1 = sd1.bisect_left(i[1])\n",
    "                val1 = sd1[max(0, idx1-1)]\n",
    "                val2 = sd1[min(len(sd1)-1, idx1)]\n",
    "                val = val1 if abs(val1-i[1]) <= abs(val2-i[1]) else val2\n",
    "                ret.append((val, i[2]))\n",
    "        ret.sort(key=lambda x: x[1])\n",
    "        return [i[0] for i in ret]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from sortedcontainers import SortedList\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        \"\"\"\n",
    "\n",
    "        :param rooms:\n",
    "        :param queries:\n",
    "        :return:\n",
    "        \"\"\"\n",
    "        q1 = []\n",
    "        for k,v in enumerate(queries):\n",
    "            q1.append((v[1], v[0],k))\n",
    "        q1.sort(key=lambda x: -x[0])\n",
    "        rooms.sort(key=lambda x: -x[1])\n",
    "        rooms = deque(rooms)\n",
    "        sd1 = SortedList()\n",
    "        ret = []\n",
    "        for i in q1:\n",
    "            while rooms and rooms[0][1] >= i[0]:\n",
    "                res = rooms.popleft()\n",
    "                sd1.add(res[0])\n",
    "            if len(sd1) == 0:\n",
    "                ret.append((-1, i[2]))\n",
    "            else:\n",
    "                idx1 = sd1.bisect_left(i[1])\n",
    "                val1 = sd1[max(0, idx1-1)]\n",
    "                val2 = sd1[min(len(sd1)-1, idx1)]\n",
    "                val = val1 if abs(val1-i[1]) <= abs(val2-i[1]) else val2\n",
    "                ret.append((val, i[2]))\n",
    "        ret.sort(key=lambda x: x[1])\n",
    "        return [i[0] for i in ret]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        queries2=[]\n",
    "        for i,q in enumerate(queries):\n",
    "            q.append(i)\n",
    "            queries2.append(q)\n",
    "        queries2=sorted(queries2,reverse=True,key=lambda x:x[1])\n",
    "        rooms=sorted(rooms,reverse=True,key=lambda x:x[1])\n",
    "        idx=0\n",
    "        bilist=[]\n",
    "        ans=[999999999]*len(queries)\n",
    "        for q in queries2:\n",
    "            while idx<len(rooms) and rooms[idx][1]>=q[1]:\n",
    "                bisect.insort(bilist,rooms[idx][0])\n",
    "                idx+=1\n",
    "            t=bisect.bisect_left(bilist,q[0])\n",
    "            if t<len(bilist) and abs(bilist[t]-q[0])<abs(ans[q[2]]-q[0]):\n",
    "                ans[q[2]]=bilist[t]\n",
    "            t=t-1\n",
    "            if t>=0 and t<len(bilist) and abs(bilist[t]-q[0])<=abs(ans[q[2]]-q[0]):\n",
    "                ans[q[2]]=bilist[t]\n",
    "        for i in range(len(ans)):\n",
    "            if ans[i]==999999999:\n",
    "                ans[i]=-1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from sortedcontainers import SortedList\n",
    "class Solution:\n",
    "    def closestRoom(self, rooms: List[List[int]], queries: List[List[int]]) -> List[int]:\n",
    "        rooms.sort(key=lambda x: -x[1])\n",
    "        for i, query in enumerate(queries):\n",
    "            query.append(i)\n",
    "        queries.sort(key=lambda x: -x[1])\n",
    "\n",
    "        ans = [0] * len(queries)\n",
    "        sl = SortedList()\n",
    "        i = 0\n",
    "        # preferred size\n",
    "        for p, s, idx in queries:\n",
    "            while i < len(rooms) and rooms[i][1] >= s:\n",
    "                sl.add(rooms[i][0])\n",
    "                i += 1\n",
    "            if sl:\n",
    "                j1 = bisect.bisect_left(sl, p)\n",
    "                # print(sl, j1, p)\n",
    "                if j1 == len(sl):\n",
    "                    ans[idx] = sl[-1]\n",
    "                elif j1 == 0:\n",
    "                    ans[idx] = sl[0]\n",
    "                else:\n",
    "                    if abs(sl[j1] - p) < abs(sl[j1 - 1] - p):\n",
    "                        ans[idx] = sl[j1]\n",
    "                    else:\n",
    "                        ans[idx] = sl[j1-1]\n",
    "            else:\n",
    "                ans[idx] = -1\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
